package leet.explore;

import common.ListNode;
import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/6/22 20:14
 */
public class Second {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            int target = -nums[i];

            while (j < k) {
                if (nums[j] + nums[k] == target) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[k]);
                    j++;
                    k--;
                    res.add(tmp);

                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }

    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }


    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        permuteCore(nums,0,res);
        return res;
    }
    private void permuteCore(int[] nums,int index,List<List<Integer>> res) {
        if (index == nums.length - 1) {
            List<Integer> tmpList = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                tmpList.add(nums[i]);
            }
            res.add(tmpList);
        } else if (index < nums.length - 1) {
            for (int i = index; i < nums.length; i++) {
                int tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;

                permuteCore(nums,index + 1,res);

                tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;
            }
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsets(res,new ArrayList<>(), nums,0);
        return res;
    }
    private void backtrackForSubsets(List<List<Integer>> res,
                                     List<Integer> tmpList,
                                     int[] nums,
                                     int start) {
        res.add(new ArrayList<>(tmpList));
        for (int i = start; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrackForSubsets(res,tmpList,nums,i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        int max = 1;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode tmp1 = l1;
        ListNode tmp2 = l2;
        ListNode head = new ListNode(-1);
        ListNode res = head;
        int carry = 0;
        int cur;
        while (tmp1 != null && tmp2 != null) {
            cur = tmp1.val + tmp2.val + carry;

            if (cur > 9) {
                cur -= 10;
                carry = 1;
            } else {
                carry = 0;
            }

            ListNode curNode = new ListNode(cur);
            head.next = curNode;
            head = head.next;
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        while (tmp1 != null) {
            cur = tmp1.val + carry;
            if (cur > 9) {
                cur -= 10;
                carry = 1;
            } else {
                carry = 0;
            }
            ListNode curNode = new ListNode(cur);
            head.next = curNode;
            head = head.next;
            tmp1 = tmp1.next;

        }
        while (tmp2 != null) {
            cur = tmp2.val + carry;

            if (cur > 9) {
                cur -= 10;
                carry = 1;
            } else {
                carry = 0;
            }

            ListNode curNode = new ListNode(cur);
            head.next = curNode;
            head = head.next;
            tmp2 = tmp2.next;
        }

        if (carry == 1) {
            head.next = new ListNode(1);
        }
        return res.next;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tmp1 = headA;
        ListNode tmp2 = headB;
        int lenA = Util.getListLen(tmp1);
        int lenB = Util.getListLen(tmp2);
        ListNode tmp3 = headA;
        ListNode tmp4 = headB;
        if (lenA > lenB) {
            // 长的先走offset步
            for (int i = 0; i < lenA - lenB; i++) {
                tmp3 = tmp3.next;
            }
            while (tmp3 != tmp4) {
                tmp3 = tmp3.next;
                tmp4 = tmp4.next;
            }
            return tmp3;
        } else {
            // 长的先走offset步
            for (int i = 0; i < lenB - lenA; i++) {
                tmp4 = tmp4.next;
            }
            while (tmp3 != tmp4) {
                tmp3 = tmp3.next;
                tmp4 = tmp4.next;
            }
            return tmp3;
        }
    }

    public int getSum(int a, int b) {
        int sum,carry;
        do {
            sum = a ^ b;
            carry = (a & b) << 1;
            a = sum;
            b = carry;
        }while (b != 0);
        return sum;
    }
    // 1.bf 2.sort [n/2] 3.遍历一次,遇到不同的计数减1
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                res = nums[i];
                cnt++;
                continue;
            }
            if (nums[i] == res) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return res;
    }
    // 1.bf 2.Sliding Window 3.Sliding Window Optimized
    public int lengthOfLongestSubstringI(String s) {
        if (s == null || s.length() < 1) {
            return  0;
        }
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String tmp = s.substring(i,j);
                if (Util.isUniqueStr(tmp) && tmp.length() > res.length()) {
                    res = tmp;
                }
            }
        }
        return res.length();
    }
    public int lengthOfLongestSubstringII(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0,i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans,j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
    public int lengthOfLongestSubstringIII(String s) {
        int n = s.length();
        Map<Character,Integer> map = new HashMap<>();
        int ans = 0;
        for (int j = 0,i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)),i);
            }
            ans = Math.max(ans,j - i + 1);
            map.put(s.charAt(j),j + 1);
        }
        return ans;
    }


    /**
     * 1.bf tle...  2.中心扩展法
     * @param s
     * @return
     */
    public String longestPalindromeI(String s) {
        if (s == null || s.length() < 1) {
            return null;
        }
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String tmp = s.substring(i,j);
                if (Util.isPalindrome(tmp) && tmp.length() > res.length()) {
                    res = tmp;
                }
            }
        }
        return res;
    }
    public String longestPalindromeII(String s) {
        String res = "";
        if (s == null || s.length() < 1) {
            return res;
        }
        int start = 0,end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s,i,i);
            int len2 = expandAroundCenter(s,i,i + 1);
            int len = Math.max(len1,len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end + 1);
    }
    private int expandAroundCenter(String s, int left, int right) {
        int L = left;
        int R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

    // 1.bf 2.保存状态
    public boolean increasingTripletI(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] < nums[j] && nums[j] < nums[k]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean increasingTripletII(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int small = Integer.MAX_VALUE,big = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) {
                small = n;
            } else if (n <= big) {
                big = n;
            } else {
                return true;
            }
        }
        return false;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length < 1) {
            return null;
        }
        return buildTreeCore(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);

    }
    private TreeNode buildTreeCore(int[] preorder,int preSt,int preEnd, int[] inorder,int inSt,int inEnd) {
        if (preSt > preEnd || inSt > inEnd || preEnd >= preorder.length || inEnd >= inorder.length) {
            return null;
        }
        int rootVal = preorder[preSt];
        int rootIndexInOrder = 0;
        for (int i = inSt; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndexInOrder = i;
            }
        }
        int offset = rootIndexInOrder - inSt;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTreeCore(preorder,preSt + 1,preSt + offset,inorder,inSt,rootIndexInOrder - 1);
        root.right = buildTreeCore(preorder,preSt + offset + 1,preEnd,inorder,rootIndexInOrder + 1,inEnd);
        return root;
    }

    public int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public boolean canJump(int[] nums) {
        if (nums == null || nums.length < 1) {
            return false;
        }
        int cur = 0;
        int next = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (cur < i) {
                cur = next;
                if (next < i) {
                    return false;
                }
            }
            next = Math.max(next,i + nums[i]);
        }
        return next >= nums.length - 1;
    }

    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        int n = coins.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[0][i] = max;
            if (i - coins[0] >= 0 && dp[0][i - coins[0]] != max) {
                dp[0][i] = dp[0][i - coins[0]] + 1;
            }
        }

        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= amount; j++) {
                left = max;
                if (j - coins[i] >= 0 && dp[i][j - coins[i]] != max) {
                    left = dp[i][j - coins[i]] + 1;
                }

                dp[i][j] = Math.min(left,dp[i - 1][j]);
            }
        }
        return dp[n - 1][amount] == max ? -1 : dp[n - 1][amount];
    }

    // 1.bf mine 2.map 保存s -> list
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if (strs == null || strs.length < 1) {
            return res;
        }
        boolean[] exs = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            List<String> cur = new ArrayList<>();
            if (exs[i]) {
                continue;
            }
            cur.add(strs[i]);
            exs[i] = true;
            for (int j = i + 1; j < strs.length; j++) {
                if (isAnagram(strs[i],strs[j])) {
                    cur.add(strs[j]);
                    exs[j] = true;
                }
            }
            res.add(cur);
        }
        return res;
    }
    private boolean isAnagram(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }
    /* public List<List<String>> groupAnagramsII(String[] strs) {
         if (strs.length == 0) return new ArrayList<List<String>>();
         Map<String, List> ans = new HashMap<String, List>();
         for (String s : strs) {
             char[] ca = s.toCharArray();
             Arrays.sort(ca);
             String key = String.valueOf(ca);
             if (!ans.containsKey(key)) {
                 ans.put(key,new ArrayList());
             }
             ans.get(key).add(s);
         }
         return new ArrayList<>((Collection<? extends List<String>>) ans.values());
     }
 */
    public ListNode oddEvenList(ListNode head) {
        if (head != null) {
            ListNode first = head;
            ListNode second = head.next;
            ListNode secondHead = second;

            while (second != null && second.next != null) {
                first.next = second.next;
                first = first.next;
                second.next = first.next;
                second = second.next;
            }
            first.next = secondHead;
            return head;
        }
        return head;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < curSize; i++) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(tmp);
        }
        for (int i = 0; i < res.size(); i++) {
            if (i % 2 != 0){
                Collections.reverse(res.get(i));
            }
        }
        return res;
    }

    public void sortColors(int[] nums) {
        int zero = 0;
        int two = nums.length - 1;
        int cur = 0;
        while (cur <= two) {
            if (nums[cur] == 0) {
                nums[cur] = nums[zero];
                nums[zero] = 0;
                zero++;
            }
            if (nums[cur] == 2) {
                nums[cur] = nums[two];
                nums[two] = 2;
                two--;
                cur--;
            }
            cur++;
        }
    }
    // mine
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        inOrder(root, res);
        return res.get(k - 1);
    }
    public void inOrder(TreeNode root, ArrayList<Integer> list) {
        if (root != null) {
            inOrder(root.left, list);
            list.add(root.val);
            inOrder(root.right, list);
        }
    }
    // most perfect
    public int kthSmallestII(TreeNode root, int k) {
        int count = cntNodes(root.left);
        if (k <= count) {
            return kthSmallestII(root.left,k);
        } else if (k > count + 1) {
            return kthSmallestII(root.right,k - count - 1);
        }
        return root.val;
    }
    private int cntNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return cntNodes(root.left) + cntNodes(root.right) + 1;
    }

    // 遇到1 就dfs把所有临近的1变成0
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int i = 0; i < nr; i++) {
            for (int j = 0; j < nc; j++) {
                if (grid[i][j] == '1') {
                    num_islands++;
                    dfs(grid,i,j);
                }
            }
        }
        return num_islands;
    }
    private void dfs(char[][] grid,int r,int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc ||  grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0';
        dfs(grid,r - 1,c);
        dfs(grid,r + 1,c);
        dfs(grid,r,c + 1);
        dfs(grid,r,c - 1);
    }

    public boolean exist(char[][] board, String word) {
        if (board == null && word == null) {
            return true;
        }
        boolean[][] used = new boolean[ board.length][ board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j] &&
                        existCore(board,word,used,i,j,0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean existCore(char[][] board, String word,boolean[][] used,int i,int j,int index) {
        if (index == word.length()) {
            return true;
        }
        if (i >= board.length || i < 0 ||
                j >= board[0].length ||
                j < 0 ||
                used[i][j] ||
                board[i][j] != word.charAt(index)) {
            return false;
        }

        used[i][j] = true;
        if (existCore(board,word,used,i - 1,j,index + 1) ||
                existCore(board,word,used,i + 1,j,index + 1) ||
                existCore(board,word,used,i,j - 1,index + 1) ||
                existCore(board,word,used,i ,j + 1,index + 1)) {
            return true;
        }

        used[i][j] = false;
        return false;
    }

    public List<String> generateParenthesis(int n) {
        char[] str = new char[n * 2];
        List<String> list = new LinkedList<>();
        addParen(list,n,n,str,0);
        return list;
    }
    private void addParen(List<String> list, int leftRem,
                          int rightRem,char[] str, int count) {
        if (leftRem < 0 || rightRem < leftRem) {
            return;
        }
        if (leftRem == 0 && rightRem == 0) {
            list.add(String.valueOf(str));
        } else {
            if (leftRem > 0) {
                str[count] = '(';
                addParen(list,leftRem - 1,rightRem,str,count + 1);
            }
            if (rightRem > leftRem) {
                str[count] = ')';
                addParen(list,leftRem,rightRem - 1,str,count + 1);
            }
        }
    }

    public int evalRPN(String[] tokens) {
        LinkedList<String> stack = new LinkedList<>();
        for (String s : tokens) {
            if ("+".equals(s) || "-".equals(s)
                    || "*".equals(s) || "/".equals(s)) {
                int op2 = Integer.parseInt(stack.pop());
                int op1 = Integer.parseInt(stack.pop());
                switch (s) {
                    case "+" : stack.push(String.valueOf(op1 + op2)); break;
                    case "-" : stack.push(String.valueOf(op1 - op2)); break;
                    case "*" : stack.push(String.valueOf(op1 * op2)); break;
                    case "/" : stack.push(String.valueOf(op1 / op2)); break;
                }
            } else {
                stack.push(s);
            }
        }
        return Integer.parseInt(stack.peek());
    }


    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (!set.contains(n)) {
            if (n == 1) {
                return true;
            }
            set.add(n);
            n = sumOfSquares(n);
        }
        return false;
    }
    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }

    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        boolean neg = false;

        if (n < 0) {
            neg = true;
            n = -n;
        }

        double ret = 1.0;
        ret = myPow(x,n >> 1);
        ret *= ret;
        if ((n & 1) != 0) {
            ret *= x;
        }
        if (neg) {
            ret = 1.0 / ret;
        }
        return ret;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1 || matrix[0] == null || matrix[0].length < 1) {
            return false;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col - 1;
        while (i < row && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 1) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        res[0] = findFirstIndex(nums,target);
        res[1] = findLastIndex(nums,target);
        return res;
    }
    private int findFirstIndex(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > target) {
                hi = mid - 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else if (mid != 0 && nums[mid] == target && nums[mid - 1] == target) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    private int findLastIndex(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > target) {
                hi = mid - 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else if (mid != nums.length - 1 && nums[mid] == target && nums[mid + 1] == target) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    public int search(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        int lo = 0;
        int hi = nums.length - 1;

        while (lo < hi) {
            int mid = (lo + hi) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] >= nums[lo]) {
                if (target < nums[mid] && target >= nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return nums[lo] == target ? lo : -1;
    }

    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.length - 1;
    }
    public int findPeakElementII(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int n : nums) {
            priorityQueue.offer(n);
            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

        }
        return priorityQueue.peek();
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n: nums
                ) {
            map.put(n, map.getOrDefault(n,0) + 1);
        }
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int n: map.keySet()
                ) {
            int freq = map.get(n);
            if (bucket[freq] == null) {
                bucket[freq] = new LinkedList<>();
            }

            bucket[freq].add(n);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = bucket.length - 1; i > 0 && k > 0; i--) {
            if (bucket[i] != null) {
                List<Integer> list = bucket[i];
                res.addAll(list);
                k -= list.size();
            }
        }
        return res;
    }



   @Test
   public void test() {
        String[] nums = {"2", "1", "+", "3", "*"};
       System.out.println(evalRPN(nums));
   }


}
